package list;

import java.util.ArrayList;

/**
 * 题目：
 * 反转单链表
 *
 * @Author Gavin
 * @date 2021.12.08 22:23
 */
public class list_1 {
    /**
     * 思路：
     * 头插法
     * 操作指针就行，比较简单,画一下图
     */
    //Time:O(n) Space:O(1)
    public static ListNode solution(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode curr = head;//移动指针节点
        ListNode pre = null;//新节点的头节点
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

    //递归的方式
    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode next = head.next;
        head.next = null;
        ListNode newHead = ReverseList(next);
        next.next = head;
        return newHead;
    }

    //从尾到头打印链表的题目可以用递归，也可以先翻转再从头打印
    public static ArrayList<Integer> print2(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        if (head == null) {
            return list;
        }
        list.addAll(print2(head.next));//添加下一个节点的val
        list.add(head.val);//添加本节点的val
        return list;
    }
}
